package leetcode.tree;

import leetcode.tree.Codec.*;

/**
 * @author : zx
 * @version V1.0
 */
public class 二叉树中的链表 {

    public static class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
    }

    /**
     * 给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
     *
     * 如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
     *
     * 一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
     *
     *  
     *
     * 示例 1：
     *
     *
     *
     * 输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
     * 输出：true
     * 解释：树中蓝色的节点构成了与链表对应的子路径。
     * 示例 2：
     *
     *
     *
     * 输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
     * 输出：true
     * 示例 3：
     *
     * 输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
     * 输出：false
     * 解释：二叉树中不存在一一对应链表的路径。
     *  
     *
     * 提示：
     *
     * 二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
     * 链表包含的节点数目在 1 到 100 之间。
     * 二叉树包含的节点数目在 1 到 2500 之间。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/linked-list-in-binary-tree
     */
    static class Solution {
        /**
         * 重点在于先固定一头 再去遍历列表
         * @param head
         * @param root
         * @return
         */
        public boolean isSubPath(ListNode head, TreeNode root) {
            if(root == null) return false;
            return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
        }

        private static boolean dfs(ListNode next, TreeNode node){
            if (next == null) return true;
            if (node == null || node.val != next.val)return false;
            return dfs(next.next, node.left) || dfs(next.next, node.right);
        }
    }

    public static void main(String[] args){
        TreeNode c = Codec.deserialize(
                "[1,10,7,10,8,6,1,10,7,1,10,4,3,9,null,10,10,4,10,7,1,3,7,null,null,7,9,6,3,null,null,8,10,10,3,1,1,null,null,null,null,null,2,null,null,10,3,5,null,null,null,6,null,5,null,null,6,2,5,null,4,null,10,9,10,null,null,null,3,10,8,5,6,null,7,3,null,8,9,6,2,null,8,9,10,10,null,4,6,4,null,null,2,5,6,null,null,null,null,6,null,1,null,null,null,null,8,null,null,10,10,null,null,null,8,null,null,3,10,null,null,10,2,null,null,7,6,null,null,null,null,null,null,null,null,null,null,4,null,null,10,null,2,null,null,1,6,null,null,8,9,null,null,null,8,4,null,null,null,10,4,null,1,null,null,null,null,9,null,null,null,null,null,9,null,10,1,6,null,null,null,null,null,null,null,5,null,2,10,null,null,null,null,null,null,null,6,null,5]");
        int[] a = new int[]{10,7,4,10,2,6,10,10,10,1,10,6};
        ListNode head = new ListNode(a[0]);
        ListNode pre = head;
        for (int i = 1; i < a.length; i++ ){
            pre.next = new ListNode(a[i]);
            pre = pre.next;
        }
        System.out.println(new Solution().isSubPath(head, c));
    }
}
